package cxydmmszl.tmp.t6.hard;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * Manacher 算法进阶问题
 * <li style="color: green;">Desc</li>
 * 给定一个字符串 str，想通过添加字符的方式使得 str 整体都变成回文字符串，
 * 但要求只能在 str 的末尾添加字符，请返回在 str 后面添加的最短字符串。
 * <br/><br/>[举例]<br/>
 * str = "abcd123321"，在必须包含最后一个字符的情况下，最长的回文子串是 "123321"，
 * 之前不是最长回文子串的部分是 "abcd"，所以末尾应该添加的部分就是 "dcba"。
 * <br/><br/>[要求]<br/>
 * 如果 str 的长度为 N，解决进阶问题的时间复杂度为 O(N)。<br/>
 * <b>保证输入数据无回文串</b>
 * <br/><br/>备注：<br/>
 * 设 N 表示输入字符串的长度<br/>
 * 保证输入字符中只含有小写字母及数字<br/>
 * 1⩽N⩽5∗10^5
 * <li style="color: green;">Input</li>
 * 输入为一个字符串str
 * <li style="color: green;">Output</li>
 * 输出一个字符串。
 * <li style="color: blue;">Link</li> CD86
 *
 * @author habitplus
 * @since 2021-11-03 10:44
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();

        str = shortestEnd(str);
        System.out.println(str);
    }

    public static String shortestEnd(String str) {
        if (str == null || str.length() < 1) return "";

        char[] chs = manacherString(str);
        int n = chs.length;
        int[] pArr = new int[n];
        int pR = -1;
        int index = -1;
        int maxContainsEnd = -1;
        for (int i = 0; i < n; i++) {
            pArr[i] = pR > i ? Math.min(pArr[index * 2 - i], pR - i) : 1;
            while (i + pArr[i] < n && i - pArr[i] > -1) {
                if (chs[i + pArr[i]] != chs[i - pArr[i]]) break;
                pArr[i]++;
            }

            if (i + pArr[i] > pR) {
                pR = pArr[i] + i;
                index = i;
            }

            if (pR == n) {
                maxContainsEnd = pArr[i];
                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = str.length() - maxContainsEnd; i >= 0; i--) {
            sb.append(chs[i * 2 + 1]);
        }
        return sb.toString();
    }

    private static char[] manacherString(String str) {
        char[] ch = str.toCharArray();
        char[] res = new char[ch.length * 2 + 1];
        int j = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : ch[j++];
        }
        return res;
    }
}
